// ClimbingStairs.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//You are climbing a stair case. It takes n steps to reach to the top.

//Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 
int climbStairs(int n) 
{
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
	if(n==0) return 0;
    if(n==1) return 1;
    if(n== 2) return 2;
    return climbStairs(n-1)+ climbStairs(n-2);
    
}

int climbStairs_2(int n)
{
	if(n==0) return 0;
    if(n==1) return 1;
	if(n== 2) return 2;
 
	int nBackone= 2;
	int nBacktwo = 1;
	int fibN = 0;
	for(int i = 3; i<=n; i++)
	{
		fibN= nBackone+nBacktwo;
		nBacktwo = nBackone;
		nBackone = fibN;
	}
	return fibN;
}

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

